Binary Search in XSLT

By Dimitre Novatchev

Language	XSLT
Category	designpatterns, xml, msxml
Posted	09 Mar 2001
Updated	09 Mar 2001

Summary

This is an XSLT implementation of the traditional and very popular algorithm for searching in a sorted array. This implementation is recursive and demonstrates the use of the "*" and "div" operators, as well as the "floor()" function.

We need to have a very efficient way of finding whether a particular object (a number, a string, a date,à etc.) belongs to a sorted set of (identically typed) objects. The only property these objects must have is a ô<ö relation, so that a set of them can be sorted and for any two objects a and b exactly one of the following holds true:

	a < b
or
	a = b
or
	a > b

It is straightforward to calculate the complexity of Binary Search û as a comparison is made for every half-interval searching for an element in a set of N elements will need not more than Log2(N) comparisons.

I used a traditional C implementation û the conversion to XSLT is almost straightforward.

A recursively called named template has to be used as XSLT does not allow incrementing counters or changing the value of a variable.

For reasons of simplicity IÆm using numbers, but their values may hint us that these are actually dates.

The sorted structure, against which the algorithm will search is specified in the following source xml document:

<dates>
  <date value="19271003" />
  <date value="19321004" />
  <date value="19530323" />
  <date value="19640505" />
  <date value="19920714" />
  <date value="19990417" />
  <date value="20001123" />
  <date value="20010406" />
  <date value="20020417" />
  <date value="20100714" />
</dates>

The binSearch template has the following parameters:

<xsl:template name="binSearch">
  <xsl:param name="argNumber" select="-Infinity" />
  <xsl:param name="nodeSet" select="/.." />
  <xsl:param name="First" select="Infinity" />
  <xsl:param name="Last" select="0" />

and their meaning is:

argNumber is the number to be searched for.

NodeSet is the node-set of sorted nodes, against which the search is performed.

First is the starting position of the interval of nodes against which the search is performed.

Last is the ending position of the interval of nodes against which the search is performed.

Note how the ômiddle pointö is calculated:

<xsl:variable name="Mid" select="floor(($First + $Last) div 2)"/>

Apart from this the code should be quite easy to understand.

As its counterpart in other programming languages, this implementation will be heavily used in other snippets implementing many interesting and important algorithms. One is validation, finding whether a given string belongs to a set of strings. Another is sorting.

HereÆs the complete stylesheet:

<xsl:stylesheet version="1.0"
    xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
>
  <xsl:output method="text"/>
 <xsl:variable name="theNumber" select="20001123"/>

 <xsl:template match="/">
  <xsl:call-template name="binSearch">
   <xsl:with-param name="argNumber" select="$theNumber"/>
   <xsl:with-param name="nodeSet" select="dates/date/@value"/>
   <xsl:with-param name="First" select="1"/>
   <xsl:with-param name="Last" select="count(dates/date/@value)"/>
  </xsl:call-template>
 </xsl:template>

 <xsl:template name="binSearch">
  <xsl:param name="argNumber" select="-Infinity"/>
  <xsl:param name="nodeSet" select="/.."/>
  <xsl:param name="First" select="Infinity"/>
  <xsl:param name="Last" select="0"/>

  <xsl:choose>
   <xsl:when test="$First > $Last">
     -1
   </xsl:when>
   <xsl:otherwise>
    <xsl:variable name="Mid"                  select="floor(($First + $Last) div 2)"/>


     <xsl:choose>
        <xsl:when test="$argNumber = $nodeSet[$Mid]">
           <xsl:value-of select="$Mid"/>
         </xsl:when>
         <xsl:when test="$argNumber &lt; $nodeSet[$Mid]">
           <xsl:call-template name="binSearch">
              <xsl:with-param name="argNumber" select="$argNumber"/>
              <xsl:with-param name="nodeSet" select="$nodeSet"/>
              <xsl:with-param name="First" select="$First"/>
              <xsl:with-param name="Last" select="$Mid - 1"/>
           </xsl:call-template>
         </xsl:when>
         <xsl:when test="$argNumber > $nodeSet[$Mid]">
           <xsl:call-template name="binSearch">
              <xsl:with-param name="argNumber" select="$argNumber"/>
              <xsl:with-param name="nodeSet" select="$nodeSet"/>
              <xsl:with-param name="First" select="$Mid + 1"/>
              <xsl:with-param name="Last" select="$Last"/>
           </xsl:call-template>
         </xsl:when>
         <xsl:otherwise>
             ERRROR
         </xsl:otherwise>
       </xsl:choose>
   </xsl:otherwise>

  </xsl:choose>
</xsl:template>

</xsl:stylesheet>

When applied on the source xml document above, it produces the correct result:

That is, 20001123 is the seventh in the sorted set represented by the source xml document.

XML Source

XSL Stylesheet

XML/HTML Result:

Text Result: